﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【进阶】52.排序3



//【头文件包含】
#include"Sort.h"
#include<time.h>


//【结构体声明】

//【函数声明】
/*测试用例-单排序*/void Test1(); void Test2(); void Test3(); void Test4(); void Test5(); void Test6(); void Test7(); void Test8(); void Test9();
/*测试用例-性能测试*/void TestOP();



//【主函数】
int main()
{
	Test1();Test2();
	
	Test3();Test4();
	
	Test5();Test6();Test7();
	
	Test8();Test9();
	
	TestOP();

	MergeSortFile("SortText.txt");
	return 0;
}

//【函数定义】
/*测试用例*/void Test1()
{
	printf("****测试用例开始****\n直接插入排序\n");
	int arr[] = { 2,8,9,7,6,5,1,3 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	InsertSort(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");

}
/*测试用例*/void Test2()
{
	printf("****测试用例开始****\n希尔排序\n");
	int arr[] = { 11,24,4,2,8,9,7,6,5,1,3,2,0,11,9,26,16 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	ShellSort(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例*/void Test3()
{
	printf("****测试用例开始****\n直接选择排序\n");
	int arr[] = { 11,5,1,3,2,0,11,9,26,16 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	SelectSort(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例*/void Test4()
{
	printf("****测试用例开始****\n堆排序\n");
	int arr[] = { 2,0,11,11,5,1,3,9,26,16 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	HeapSort(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例*/void Test5()
{
	printf("****测试用例开始****\n冒泡排序\n");
	int arr[] = { 5,1,3,9,2,0,11,8,9,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	BubbleSort(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例*/void Test6()
{
	printf("****测试用例开始****\n快速排序-递归\n");
	int arr[] = { 2,0,11,9,26,0,11,8,9,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	QuickSort(arr,0,sz-1);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例*/void Test7()
{
	printf("****测试用例开始****\n快速排序-非递归\n");
	int arr[] = { 1,9,26,0,2,0,111,8,9,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	QuickSortNonR(arr, 0, sz - 1);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例*/void Test8()
{
	printf("****测试用例开始****\n归并排序-递归\n");
	int arr[] = { 1,9,26,0,2,0,11,1,8,9,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	MergeSort(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}/*测试用例*/void Test9()
{
	printf("****测试用例开始****\n归并排序-非递归\n");
	int arr[] = { 9,26,16,1,9,26,0,2,0,11,5,1,3,11,1,8,9,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	MergeSortNonR(arr, sz);
	PrintArr(arr, sz);
	printf("****测试用例结束****\n");
}
/*测试用例-性能测试*/void TestOP()
{
	printf("****测试用例开始****\n");
	//测试排序的性能对比
	srand(time(0));
	const int N = 20000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	for (int i = 0;i < N;++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];a3[i] = a1[i];
		a4[i] = a1[i];a5[i] = a1[i];
		a6[i] = a1[i];a7[i] = a1[i];
	}
	int begin1 = clock();InsertSort(a1,N);int endl = clock();
	int begin2 = clock();ShellSort(a2,N);int end2 = clock();
	int begin3 = clock();SelectSort(a3, N);int end3 = clock();
	int begin4 = clock();HeapSort(a4,N);int end4 = clock();
	int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock();
	int begin6 = clock();MergeSort(a6, N);int end6 = clock();
	int begin7 = clock();BubbleSort(a7,N);int end7 = clock();
	
	printf("InsertSort: %d\n",endl - begin1);
	printf("she11Sort:  %d\n",end2 - begin2);
	printf("SelectSort: %d\n",end3 - begin3);
	printf("HeapSort:   %d\n",end4 - begin4);
	printf("BubbleSort: %d\n",end7 - begin7);
	printf("QuickSort:  %d\n",end5 - begin5);
	printf("MergeSort:  %d\n",end6 - begin6);

	free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
	printf("****测试用例结束****\n");
}


//【笔记】
//52.排序：使一串记录按其中某个关键字大小递增或递减的操作
	//交换排序：
		// 快速排序：选出一个Key位置，将左边右边分别调整为比Key位置小或大的元素，Key的位置就被固定了，然后依次递归左右部分
			//首先需要创建一个一次快排的子函数，该函数可以把1个值排列到正确的位置并返回该位置下标
			// 之后利用该子函数得到拆分左右的位置，并将其作为快排主函数新的左极和右极依次进行递归调用 
			// 在递归函数中会再分为左中右三部分直到达到左极和右极发生错位或相遇，即l>=r递归终点，依次向上回到最终
			// 顺序上相当于找到一个位置、执行位置左边、找到左边的一个正确位置、执行左边正确位置的左边...直到l>=r;
			// 执行最深层直到执行完最深的左递归函数，向上依次执行左侧剩余的右侧函数，同理再执行最外层右侧函数到最深在返回最上
			// 【需要注意】如果不做处理，假设遇到有序数组，则视为遇到最差情况，时间复杂度为O(N^2),同时因为递归过深会导致栈溢出
				//因此需要在子函数-一次快排时做特殊处理，取被排数组收尾和中间三个元素取中值换到视为key的一端，
				// 这样保证每次被分解的下层递归数组的长度缩短约一半，减少平均递归深度提高效率  
			//通过【三数取中】可将快速排序优化至平均 时间-O(N*log_2_N) 空间O(log_2_N);
		//归并排序：单趟排序思想是合并两端有序数组合并后依旧有序
			// 所以要一直向下递归至最小，从最小数组开始有序，一直返回到最上，需要开辟一个和原数组大小一致的空间来进行替换和覆盖
			//时间O（N*log_2_n） 空间O(N);